package org.usmile.algorithms.leetcode.simple;

import java.util.ArrayList;
import java.util.List;

/**
 * 163. 缺失的区间
 *
 * 给定一个排序的整数数组 nums ，其中元素的范围在 闭区间 [lower, upper] 当中，返回不包含在数组中的缺失区间。
 *
 * 示例：
 *
 * 输入: nums = [0, 1, 3, 50, 75], lower = 0 和 upper = 99,
 * 输出: ["2", "4->49", "51->74", "76->99"]
 */
public class _0163 {
}

class _0163_Solution {
    public List<String> findMissingRanges(int[] nums, int lower, int upper) {
        List<String> res = new ArrayList<>();
        long pre = lower - 1;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == pre + 2) {
                res.add(String.valueOf(pre + 1));
            } else if (nums[i] > pre + 2) {
                res.add((pre + 1) + "->" + (nums[i] - 1));
            }

            pre = nums[i];
        }
        if (upper == pre + 1) {
            res.add(String.valueOf(pre + 1));
        } else if (upper > pre + 1) {
            res.add((pre + 1) + "->" + upper);
        }

        return res;
    }
}

class _0163_Solution1 {
    public List<String> findMissingRanges(int[] nums, int lower, int upper) {
        List<String> ranges = new ArrayList<>();
        if (nums.length == 0) {
            if (lower == upper) {
                ranges.add(lower + "");
            } else {
                ranges.add(lower + "->" + upper);
            }

            return ranges;
        }

        if (nums[0] > lower) {
            if (nums[0] == lower + 1) {
                ranges.add(Integer.toString(lower));
            } else {
                ranges.add(lower + "->" + (nums[0] - 1));
            }
        }

        int i = 0;
        while (i < nums.length) {
            while (i < nums.length - 1 && nums[i] + 1 == nums[i + 1]) {
                i++;
            }
            if (i < nums.length - 1) {
                if (nums[i + 1] == nums[i] + 2) {
                    ranges.add((nums[i] + 1) + "");
                } else {
                    ranges.add((nums[i] + 1) + "->" + (nums[i + 1] - 1));
                }
            } else {
                if (nums[i] < upper) {
                    if (nums[i] == upper - 1) {
                        ranges.add(upper + "");
                    } else {
                        ranges.add((nums[i] + 1) + "->" + upper);
                    }
                }
            }

            i++;
        }

        return ranges;
    }
}